package demon1;

public class BinarySearchTree {
    public class Node{
        int val;
        Node left;
        Node right;
        public Node(int val){
            this.val=val;
        }
    }
    public Node root=null;
    public Node search(int val){
        if(root==null){
            return null;
        }
        Node cur=root;
        while(cur!=null){
            if(cur.val<val){
                cur=cur.right;
            }else if(cur.val>val){
                cur=cur.left;
            }else {
                return cur;
            }
        }
        return null;
    }
    public boolean insert(int val){
        Node node=new Node(val);
        if(root==null){
            root=node;
        }
        Node cur=root;
        Node parent=cur;
        while(cur!=null){
            if(cur.val==val){
                return false;
            }else if(cur.val<val){
                parent=cur;
                cur=cur.left;
            }else{
                parent=cur;
                cur=cur.right;
            }
        }
        if(cur.val<val){
            cur.right=node;
        }else {
            cur.left=node;
        }
        return false;
    }
    public void remove(int val){
        Node cur=root;
        Node parent=null;
        if(root==null){
            return;
        }
        while(cur!=null){
            if(cur.val==val) {
                remove(parent,cur);
            } else if(cur.val<val){
                parent=cur;
                cur=cur.right;
            }else if(cur.val>val){
                parent=cur;
                cur=cur.left;
            }
        }
    }
    public void remove(Node parent,Node cur){
        Node target=parent;
        Node targetP=cur.right;
        if(cur.left==null){
            if(cur==root){
                root=root.right;
            }else{
                parent.left=cur.right;
            }
        }else if(cur.right==null){
            if(cur==root){
                root=root.left;
            }else{

            }
        }else{

        }
    }
}
